//dp[i]表示以i位置结尾的字符串是否可以被拼接
class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> str_set;
        for (auto& str: wordDict)
            str_set.insert(str);

        int n = s.size();
        vector<bool> dp(n + 1, true);
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j <= i; j++)
            {
                string tmp = s.substr(j, i - j + 1);
                bool is_exist = str_set.count(tmp);
                dp[i + 1] = (is_exist & dp[j]);
                if (dp[i + 1])
                    break;
            }
        }


        return dp[n];
    }
};